package LC;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * https://leetcode.com/problems/construct-binary-tree-from-inorder-and-postorder-traversal/description/
 * Given inorder and postorder traversal of a tree, construct the binary tree.
 */
public class LC_106_ConstructBinaryTreefromInorderandPostorderTraversal_Recur_Inorder_Postorder_BinaryTree {
    public static void main(String[] args) {
        int[] inorder = {0, 1, 2, 3, 4, 5, 6, 7};
        int[] postorder = {0, 2, 3, 1, 5, 7, 6, 4};
        TreeNode root = Solution.buildTree(inorder, postorder);
        List<List<Integer>> lists = levelOrder(root);
        System.out.println(lists);
    }

    static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }
    }

    static List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> resultList = new ArrayList<>();
        if (root == null)
            return resultList;
        List<Integer> levelStorage = new LinkedList<>();
        LinkedList<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        queue.offer(null);
        while (queue.size() > 1) {
            TreeNode top = queue.poll();
            if (top == null) {
                resultList.add(levelStorage);
                queue.offer(null);
                levelStorage = new LinkedList<>();
            } else {
                levelStorage.add(top.val);
                if (top.left != null)
                    queue.offer(top.left);
                if (top.right != null)
                    queue.offer(top.right);
            }
        }
        resultList.add(levelStorage);
        return resultList;
    }

    static class Solution {
        static TreeNode buildTree(int[] inorder, int[] postorder) {
            if (inorder == null || postorder == null || inorder.length == 0 || inorder.length != postorder.length)
                return null;
            return solve(inorder, 0, inorder.length - 1, postorder, 0, postorder.length - 1);
        }

        private static TreeNode solve(int[] inorder, int x, int y, int[] postorder, int i, int j) {
            if (x >= 0 && x <= y && i >= 0 && i <= j) {
                if (x == y)
                    return new TreeNode(postorder[j]);
                else if (x < y) {
                    TreeNode root = new TreeNode(postorder[j]);
                    int idx = x;
                    while (idx < y && inorder[idx] != postorder[j]) idx++;

                    int leftLength = idx - x;
                    if (leftLength > 0) root.left = solve(inorder, x, idx - 1, postorder, i, i + leftLength - 1);
                    int rightLength = y - idx;
                    if (rightLength > 0)
                        root.right = solve(inorder, idx + 1, y, postorder, i + leftLength, j - 1);
                    return root;
                } else
                    return null;
            }
            return null;
        }
    }
}
